|
In mathematics, and specifically graph theory, Paley graphs, named after Raymond Paley, are dense undirected graphs constructed from the members of a suitable finite field by connecting pairs of elements that differ by a quadratic residue. The Paley graphs form an infinite family of conference graphs, which yield an infinite family of symmetric conference matrices. Paley graphs allow graph-theoretic tools to be applied to the number theory of quadratic residues, and have interesting properties that make them useful in graph theory more generally. Paley graphs are closely related to the Paley construction for constructing Hadamard matrices from quadratic residues . They were introduced as graphs independently by and . Sachs was interested in them for their self-complementarity properties, while Erdős and Rényi studied their symmetries. Paley digraphs are directed analogs of Paley graphs that yield antisymmetric conference matrices. They were introduced by (independently of Sachs, Erdős, and Rényi) as a way of constructing tournaments with a property previously known to be held only by random tournaments: in a Paley digraph, every small subset of vertices is dominated by some other vertex. == Definition == Let ''q'' be a prime power such that ''q'' = 1 (mod 4). That is, ''q'' should either be an arbitrary power of a Pythagorean prime (a prime congruent to 1 mod 4) or an even power of an odd non-Pythagorean prime. Note that this implies that the unique finite field of order ''q'', F''q'', has a square root of −1. Now let ''V'' = F''q'' and :. This set is well defined since ''a'' − ''b'' = −(''b'' − ''a''), and since −1 is a square, it follows that ''a'' − ''b'' is a square if and only if ''b'' − ''a'' is a square. By definition ''G'' = (''V'', ''E'') is the Paley graph of order ''q''. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Paley graph」の詳細全文を読む スポンサード リンク
|